星尘

541. 反转字符串 II

发表于 更新于 分类于

541. 反转字符串 II

题目

给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。

  • 如果剩余字符少于 k 个，则将剩余字符全部反转。
  • 如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。

示例 1:

1
2
输入：s = "abcdefg", k = 2
输出："bacdfeg"

示例 2:

1
2
输入：s = "abcd", k = 2
输出："bacd"

题解

需要借助上一题的反转字符串的方法。

根据题意可知，剩余字符超过或者小于 k 个，都会进行反转。所以每次都取 k 个元素进行反转，如果不足 k 个，那么就反转剩余的不足的 k 个的元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution(object):
    def reverseStr(self, s, k):
        """
        :type s: str
        :type k: int
        :rtype: str
        """
        s = list(s)
        size = len(s)

        # 反转子字符串
        def reverse_substring(data):
            left = 0
            right = len(data) - 1
            while left < right:
                data[left], data[right] = data[right], data[left]
                left += 1
                right -= 1
            return data

        # 2 * k 是步长, s[x : x + k] 是对 2 * k 的一半进行操作
        for x in range(0, size, 2 * k):
            s[x : x + k] = reverse_substring(s[x : x + k])

        return "".join(s)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
func reverseStr(s string, k int) string {
	ss := []byte(s)
	size := len(s)

	for x := 0; x < size; x += 2 * k {
		// python 和 go 的切片区别在于 python 如果切片超过范围，那么剩余多少个元素就取多少个
		// go 则不一样，假如切片需要取 4 个, 但是最后只有 3 个, 那么 go 会扩容, 最后取到的结果为 3 个元素加一个 nul。python 则就是 3 个元素
		if x +k < size{
			reverseSubstring(ss[x: x+k])
		}else{
			reverseSubstring(ss[x: size])
		}
	}
	return string(ss)
}

func reverseSubstring(data []byte){
	left := 0
	right := len(data) -1
	for left < right{
		data[left], data[right] = data[right], data[left]
		left +=1
		right -=1
	}
}

变体

总结

参考